There is an increasing need in modern industry for data privacy and/or security. In the communications field, data being transmitted via radio communication or telephone lines is susceptible of interception and unauthorized use or alteration. In the computer industry the unauthorized access to data may be obtained for example by accessing various storage devices or intercepting messages being transmitted between terminals or between the terminals and the host of remote-access computer networks. In such networks a large number of subscribers are provided access to "data banks" for receiving, storing, processing and furnishing information of a confidential nature. The need for data security in such systems cannot be too highly emphasized.
Generally, present-day computing centers have elaborate procedures for maintaning physical security at the location where the central processor and data-storage facilities are located. For example, some of the procedures which have been used are: restriction of personnel within the computer center, utilization of mechanical keys for activation of equipment, and camera surveillance. These security procedures, while providing a measure of safety in keeping unauthorized individuals from the physical computing center itself, are not effective with respect to large remote-access computer networks which have many terminals located at distant sites, connected to the central processor by either cable or telecommunication lines.
Some digital techniques have been implemented in computing systems for the purpose of maintaining privacy of data. One such approach is the use of a device generally known as "memory protection". This type of data security technique associates a unique binary key with selected segments of the storage within the central processor. Then, internal to the processor, there are present various protection circuits that check for a match of the binary key during the operation of executable instructions and accesses to sections of storage. This type of security measure is generally ineffective in protecting information within the computing system from unauthorized individuals who have knowledge of the computing system circuitry, and who can devise sophisticated programming techniques for illegally obtaining unauthorized access to data.
In the field of communications, cryptography has long been recognized as a means for achieving security and privacy. Many systems have been developed in the prior art for encrypting messages for maintaining secrecy of communications. For example, one well-known technique which has been used for generating "ciphertext" from "plaintext" messages is of substitution. In systems which utilize substitution, letters or symbols that comprise the clear message are replaced by some other symbols in accordance with a predetermined "key". The resulting substituted message is a cipher which is expected to be secret and hopefully can not be understood without the knowledge of the secret key. A particular advantage of substitution in accordance with a prescribed key is that the deciphering operation is easily implemented by reverse application of the key. A common implementation of substitution techniques may be found in ciphering-wheel devices, for example, those disclosed in U.S. Pat. Nos. 2,964,856 and 2,984,700, filed Mar. 10, 1941 and Sept. 22, 1944 respectively.
Further teachings on the design principles of more advanced substitution techniques may be found in "Communication Theory of Secrecy Devices" by C. E. Shannon, Bell System Technical Journal, Vol. 28, Pages 656-715, October 1949. Shannon, in his paper, presents further developments in the art of cryptography for expounding the product cipher, that is, the successive application of two or more distinctly different kinds of message-symbol transformation. One example of a product cipher consists of a symbol substitution followed by a symbol transposition.
Another well-known technique for enciphering a clear message communication is the use of a stream-generator sequence which is utilized to form a modulo sum with the symbol that comprise the clear message. The cipher output message stream formed by the modulo sum would then be unintelligible to the receiver of the message, if it does not have knowledge of the stream-generator sequence. Examples of such stream-generators may be found in U.S. Pat. Nos. 3,250,855 and 3,364,308, filed May 23, 1962 and Jan. 23, 1963, respectively.
Various ciphering systems have been developed in the prior art for rearranging communication data in some ordered way to provide secrecy. For example, U.S. Pat. No. 3,522,374 filed June 12, 1967 teaches the processing of a clear message with a key-material generator that controls the number of cycles for enciphering and deciphering. Related to this patent is U.S. Pat. No. 3,506,783 filed June 12, 1967 which discloses the means for generating the key-material which gives a very long pseudo-random sequence. Another approach which has been utilized in the prior art for establishing secret communications is the coding of the electrical signal representations comprising a message that are transmitted over the communications channel. This type of technique is usually more useful in preventing jamming rather than in preventing a cryptanalyst from understanding a cipher message. Exemplary systems of this type may be found in U.S. Pat. Nos. 3,411,089, filed June 28, 1962 and 3,188,390, filed June 8, 1965.
In the area of computer data communications, it has generally been found that product ciphers are superior to other types of ciphering schemes, as discussed in "Cryptography and Computer Privacy" by H. Feistel, Scientific American, Volume 228, No. 5, May 1973, pp. 15-23. Examples of product ciphering systems are disclosed in the two previously referenced U.S. Pat. Nos. 3,798,359 and 3,796,830, as well as the copending application Ser. No. 552,685. These patent references disclose systems for generating a product cipher under the control of the unique user key. With careful selection of the size of the data block and the key size, the probability of ever cracking the cipher becomes extremely small. That is, a cipher becomes impractical to crack by trial of all possible combinations of the key. This is particularly true if the ciphertext reveals no information with regard to the unique user key.
The previously referenced block cipher cryptographic systems, especially those utilizing the non-affine transformation of substitution, may be utilized to produce extremely secure ciphers. However, the price which one must pay to produce such a cipher with these systems is the iteration or repetition of the encipherment process a plurality of times. For example, 16 such rounds is often considered the minimum number to produce a cipher of satisfactory security utilizing such systems.
In an effort to effect a standard for government use which will aid government agencies in carrying out new privacy legislation, the National Bureau of Standards has recently proposed a Federal Information Processing Standards entitled, "Encryption Algorithm for Computer Data Protection". The proposed standard together with a complete technical description is contained in the Federal Register, Volume 40, No. 52, Monday, Mar. 17, 1975, on pages 12134 through 12139. The key-controlled block-ciper cryptographic system described in the NBS standard proposal is an algorithmic description of the specific hardware disclosed in the previously referenced co-pending U.S. application Ser. No. 552,685.
A problem with such block-cipher cryptographic systems is that any given block of data x will be transferred into an output block y, and further, assuming that the same key is used in all instances, identical x's will always produce identical y's in the output. As will be discussed more fully subsequently with respect to FIGS. 4A through 4E, this can be a problem where there are large strings of identical blocks occurring in a given record to be encrypted. Such, for example, is source code for a computer, wherein many blanks exist.
Further, the above-referenced block-cipher systems assume in each instance that a full data block is received, and any short blocks must be artifically padded prior to the encryption and sent out in the full block form. This is disadvantageous in a number of respects, since it requires the storage of unnecessary or non-information-bearing data in storage or correspondingly requires the transmitting of such non-information-bearing data.